{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Non Negative Product in a Matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxProductPath"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #矩阵的最大非负积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个大小为 <code>m x n</code> 的矩阵 <code>grid</code> 。最初，你位于左上角 <code>(0, 0)</code> ，每一步，你可以在矩阵中 <strong>向右</strong> 或 <strong>向下</strong> 移动。</p>\n",
    "\n",
    "<p>在从左上角 <code>(0, 0)</code> 开始到右下角 <code>(m - 1, n - 1)</code> 结束的所有路径中，找出具有 <strong>最大非负积</strong> 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。</p>\n",
    "\n",
    "<p>返回 <strong>最大非负积 </strong>对<strong><em> </em><code>10<sup>9</sup>&nbsp;+ 7</code></strong> <strong>取余</strong> 的结果。如果最大积为 <strong>负数</strong> ，则返回<em> </em><code>-1</code> 。</p>\n",
    "\n",
    "<p><strong>注意，</strong>取余是在得到最大积之后执行的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/12/23/product1.jpg\" style=\"width: 244px; height: 245px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>从 (0, 0) 到 (2, 2) 的路径中无法得到非负积，所以返回 -1 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/12/23/product2.jpg\" style=\"width: 244px; height: 245px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,-2,1],[1,-2,1],[3,-4,1]]\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：</strong>最大非负积对应的路径如图所示 (1 * 1 * -2 * -4 * 1 = 8)\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/12/23/product3.jpg\" style=\"width: 164px; height: 165px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,3],[0,-4]]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>最大非负积对应的路径如图所示 (1 * 0 * -4 = 0)\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 15</code></li>\n",
    "\t<li><code>-4 &lt;= grid[i][j] &lt;= 4</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-non-negative-product-in-a-matrix](https://leetcode.cn/problems/maximum-non-negative-product-in-a-matrix/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-non-negative-product-in-a-matrix](https://leetcode.cn/problems/maximum-non-negative-product-in-a-matrix/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]]', '[[1,-2,1],[1,-2,1],[3,-4,1]]', '[[1,3],[0,-4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dx, dy = [1, 0], [0, 1]\n",
    "        t = [[[0, 0] for _ in range(n)] for _ in range(m)]\n",
    "        t[0][0] = [grid[0][0], grid[0][0]]\n",
    "        f = False\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for k in range(2):\n",
    "                    x, y = i + dx[k], j + dy[k]\n",
    "                    if x >= m or y >= n: continue\n",
    "                    t[x][y][0] = min(t[x][y][0], t[i][j][0] * grid[x][y], t[i][j][1] * grid[x][y])\n",
    "                    t[x][y][1] = max(t[x][y][1], t[i][j][0] * grid[x][y], t[i][j][1] * grid[x][y])\n",
    "                f = f|(grid[i][j]==0)\n",
    "        return t[-1][-1][1] % (10 ** 9 + 7) if t[-1][-1][1] > 0 else 0 if f else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        q, ans, m, n, dst = [[0, 0, grid[0][0], grid[0][0]]], -1, len(grid) - 1, len(grid[0]) - 1, grid[-1][-1]\n",
    "        if m == 0 and n == 0: return dst\n",
    "        vis = [[-1] * (n + 1) for _ in range(m + 1)]\n",
    "        while q:\n",
    "            q1 = []\n",
    "            for i, j, k1, k2 in q:\n",
    "                for i1, j1 in [[i+1, j], [i, j+1]]:\n",
    "                    if i1 == m and j1 == n:\n",
    "                        ans = max(ans, k1 * dst, k2 * dst)\n",
    "                    elif i1 <= m and j1 <= n:\n",
    "                        tmp = grid[i1][j1]\n",
    "                        if vis[i1][j1] < 0:\n",
    "                            vis[i1][j1] = len(q1)\n",
    "                            q1.append([i1, j1] + sorted([k1 * tmp, k2 * tmp]))\n",
    "                        else:\n",
    "                            tmp1 = q1[vis[i1][j1]]\n",
    "                            tmp2 = sorted([tmp1[2], tmp1[3], k1 * tmp, k2 * tmp])\n",
    "                            tmp1[2], tmp1[3] = tmp2[0], tmp2[-1]\n",
    "            q = q1\n",
    "        return ans % int(1e9 + 7) if ans >= 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dx, dy = [1, 0], [0, 1]\n",
    "        t = [[[0, 0] for _ in range(n)] for _ in range(m)]\n",
    "        t[0][0] = [grid[0][0], grid[0][0]]\n",
    "        f = False\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for k in range(2):\n",
    "                    x, y = i + dx[k], j + dy[k]\n",
    "                    if x >= m or y >= n: continue\n",
    "                    t[x][y][0] = min(t[x][y][0], t[i][j][0] * grid[x][y], t[i][j][1] * grid[x][y])\n",
    "                    t[x][y][1] = max(t[x][y][1], t[i][j][0] * grid[x][y], t[i][j][1] * grid[x][y])\n",
    "                f = f|(grid[i][j]==0)\n",
    "        return t[-1][-1][1] % (10 ** 9 + 7) if t[-1][-1][1] > 0 else 0 if f else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dp=[[] for i in range(n)]\n",
    "        for i in range(n):\n",
    "            if i==0:\n",
    "                dp[i].append(grid[0][0])\n",
    "                dp[i].append(grid[0][0])\n",
    "            else:\n",
    "                if grid[0][i]<0:\n",
    "                    dp[i].append(dp[i-1][1]*grid[0][i])\n",
    "                    dp[i].append(dp[i-1][0]*grid[0][i])\n",
    "                else:\n",
    "                    dp[i].append(dp[i-1][0]*grid[0][i])\n",
    "                    dp[i].append(dp[i-1][1]*grid[0][i])\n",
    "\n",
    "        \n",
    "        for i in range(1,m):\n",
    "            for j in range(n):\n",
    "                a=dp[j][1]\n",
    "                b=dp[j][0]\n",
    "                if j==0:\n",
    "                    if grid[i][j]<0:\n",
    "                        dp[j][0]=a*grid[i][j]\n",
    "                        dp[j][1]=b*grid[i][j]\n",
    "                    else:\n",
    "                        dp[j][1]=a*grid[i][j]\n",
    "                        dp[j][0]=b*grid[i][j]\n",
    "                else:\n",
    "                    if grid[i][j]<0:\n",
    "                        dp[j][0]=min(a,dp[j-1][1])*grid[i][j]\n",
    "                        dp[j][1]=max(b,dp[j-1][0])*grid[i][j]\n",
    "                    else:\n",
    "                        dp[j][1]=min(a,dp[j-1][1])*grid[i][j]\n",
    "                        dp[j][0]=max(b,dp[j-1][0])*grid[i][j]\n",
    "        \n",
    "        if dp[n-1][0]<0:\n",
    "            return -1\n",
    "        else:\n",
    "            return dp[n-1][0]%int(1e9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        max_ = [[0] * n for _ in range(m)]\n",
    "        min_ = [[0] * n for _ in range(m)]\n",
    "        max_[0][0] = min_[0][0] = grid[0][0]\n",
    "        for j in range(1, n):\n",
    "            max_[0][j] = min_[0][j] = max_[0][j-1] * grid[0][j]\n",
    "        for i in range(1, m):\n",
    "            max_[i][0] = min_[i][0] = max_[i-1][0] * grid[i][0]\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if grid[i][j] >= 0:\n",
    "                    max_[i][j] = max(max_[i][j-1], max_[i-1][j]) * grid[i][j]\n",
    "                    min_[i][j] = min(min_[i][j-1], min_[i-1][j]) * grid[i][j]\n",
    "                else:\n",
    "                    max_[i][j] = min(min_[i][j-1], min_[i-1][j]) * grid[i][j]\n",
    "                    min_[i][j] = max(max_[i][j-1], max_[i-1][j]) * grid[i][j]\n",
    "        return max_[-1][-1] % (10 ** 9 + 7) if max_[-1][-1] >= 0 else -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        maxp = [[0] * n for _ in range(m)]\n",
    "        minp = [[0] * n for _ in range(m)]\n",
    "\n",
    "        maxp[0][0] = grid[0][0]\n",
    "        minp[0][0] = grid[0][0]\n",
    "\n",
    "        for j in range(1, n):\n",
    "            maxp[0][j] = maxp[0][j-1] * grid[0][j]\n",
    "            minp[0][j] = minp[0][j-1] * grid[0][j]\n",
    "        \n",
    "        for i in range(1, m):\n",
    "            maxp[i][0] = maxp[i-1][0] * grid[i][0] \n",
    "            minp[i][0] = minp[i-1][0] * grid[i][0]\n",
    "        \n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                x = grid[i][j]\n",
    "                if x >= 0:\n",
    "                    maxp[i][j] = max(maxp[i-1][j], maxp[i][j-1]) * x\n",
    "                    minp[i][j] = min(minp[i-1][j], minp[i][j-1]) * x\n",
    "                else:\n",
    "                    maxp[i][j] = min(minp[i-1][j], minp[i][j-1]) * x\n",
    "                    minp[i][j] = max(maxp[i-1][j], maxp[i][j-1]) * x\n",
    "        return maxp[m-1][n-1] % mod if maxp[m-1][n-1] >= 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        if not grid:\n",
    "            return 0\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp1 = [[1]*n for _ in range(m)]\n",
    "        dp2 = [[1]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not i and not j:\n",
    "                    dp1[i][j] = grid[i][j]\n",
    "                    dp2[i][j] = grid[i][j]\n",
    "                if i == 0 and j != 0:\n",
    "                    dp1[i][j] = dp1[i][j-1]*grid[i][j]\n",
    "                    dp2[i][j] = dp2[i][j-1]*grid[i][j]\n",
    "                if i != 0 and j == 0:\n",
    "                    dp1[i][j] = dp1[i-1][j] * grid[i][j]\n",
    "                    dp2[i][j] = dp2[i-1][j] * grid[i][j]\n",
    "                elif i != 0 and j != 0:\n",
    "                    dp1[i][j] = max(dp1[i-1][j]*grid[i][j], dp1[i][j-1]*grid[i][j], dp2[i-1][j]*grid[i][j], dp2[i][j-1]*grid[i][j])\n",
    "                    dp2[i][j] = min(dp1[i-1][j]*grid[i][j], dp1[i][j-1]*grid[i][j], dp2[i-1][j]*grid[i][j], dp2[i][j-1]*grid[i][j])      \n",
    "        return -1 if dp1[-1][-1] < 0 else dp1[-1][-1]%1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = 10**9+7\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[[0,0] for _ in range(n)] for _ in range(m)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if(i == 0 and j == 0):\n",
    "                    dp[0][0] = [grid[0][0],grid[0][0]]\n",
    "                elif(i == 0):\n",
    "                    dp[i][j][0] = dp[i][j-1][0]*grid[i][j]\n",
    "                    dp[i][j][1] = dp[i][j-1][1]*grid[i][j]\n",
    "                elif(j == 0):\n",
    "                    dp[i][j][0] = dp[i-1][j][0]*grid[i][j]\n",
    "                    dp[i][j][1] = dp[i-1][j][1]*grid[i][j]        \n",
    "                else:\n",
    "                    dp[i][j][0] = min(dp[i-1][j][0]*grid[i][j], dp[i-1][j][1]*grid[i][j], dp[i][j-1][0]*grid[i][j], dp[i][j-1][1]*grid[i][j])\n",
    "                    dp[i][j][1] = max(dp[i-1][j][0]*grid[i][j], dp[i-1][j][1]*grid[i][j], dp[i][j-1][0]*grid[i][j], dp[i][j-1][1]*grid[i][j])\n",
    "        return dp[m-1][n-1][1] % M if dp[m-1][n-1][1] >= 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dx, dy = [1, 0], [0, 1]\n",
    "        t = [[[0, 0] for _ in range(n)] for _ in range(m)]\n",
    "        t[0][0] = [grid[0][0], grid[0][0]]\n",
    "        f = False\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for k in range(2):\n",
    "                    x, y = i + dx[k], j + dy[k]\n",
    "                    if x >= m or y >= n: continue\n",
    "                    minn = min(t[i][j][0] * grid[x][y], t[i][j][1] * grid[x][y])\n",
    "                    t[x][y][0] = min(t[x][y][0], minn)\n",
    "                    maxx = max(t[i][j][0] * grid[x][y], t[i][j][1] * grid[x][y])\n",
    "                    t[x][y][1] = max(t[x][y][1], maxx)\n",
    "                if grid[i][j] == 0:\n",
    "                    f = True\n",
    "        return t[-1][-1][1] % (10 ** 9 + 7) if t[-1][-1][1] > 0 else 0 if f else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 设 maxgt[i][j],minlt[i][j] 分别为从坐标 (0,0) 出发，到达位置 (i,j) 时乘积的最大值与最小值。\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        maxgt = [[0] * n for _ in range(m)]\n",
    "        minlt = [[0] * n for _ in range(m)]\n",
    "\n",
    "        maxgt[0][0] = minlt[0][0] = grid[0][0]\n",
    "        for i in range(1, n):\n",
    "            maxgt[0][i] = minlt[0][i] = maxgt[0][i - 1] * grid[0][i]\n",
    "        for i in range(1, m):\n",
    "            maxgt[i][0] = minlt[i][0] = maxgt[i - 1][0] * grid[i][0]\n",
    "        \n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if grid[i][j] >= 0:\n",
    "                    maxgt[i][j] = max(maxgt[i][j - 1], maxgt[i - 1][j]) * grid[i][j]\n",
    "                    minlt[i][j] = min(minlt[i][j - 1], minlt[i - 1][j]) * grid[i][j]\n",
    "                else:\n",
    "                    maxgt[i][j] = min(minlt[i][j - 1], minlt[i - 1][j]) * grid[i][j]\n",
    "                    minlt[i][j] = max(maxgt[i][j - 1], maxgt[i - 1][j]) * grid[i][j]\n",
    "        \n",
    "        if maxgt[m - 1][n - 1] < 0:\n",
    "            return -1\n",
    "        return maxgt[m - 1][n - 1] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        if not grid:\n",
    "            return 0\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        \n",
    "        dp_nega = [[0]*n for _ in range(m)]\n",
    "        dp_posi = [[0]*n for _ in range(m)]\n",
    "        tmp = 1\n",
    "        for i in range(m):\n",
    "            tmp *= grid[i][0]\n",
    "            dp_nega[i][0] = tmp \n",
    "            dp_posi[i][0] = tmp\n",
    "        \n",
    "        tmp = 1\n",
    "        for i in range(n):\n",
    "            tmp *= grid[0][i]\n",
    "            dp_nega[0][i] = tmp\n",
    "            dp_posi[0][i] = tmp\n",
    "        \n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                min_val = min(grid[i][j]*dp_nega[i-1][j],grid[i][j]*dp_nega[i][j-1],grid[i][j]*dp_posi[i-1][j],grid[i][j]*dp_posi[i][j-1])\n",
    "                \n",
    "                dp_nega[i][j] = min_val\n",
    "                max_val = max(grid[i][j]*dp_nega[i-1][j],grid[i][j]*dp_nega[i][j-1],grid[i][j]*dp_posi[i-1][j],grid[i][j]*dp_posi[i][j-1])\n",
    "                \n",
    "                dp_posi[i][j] = max_val\n",
    "        \n",
    "        return dp_posi[-1][-1]%(10**9+7) if dp_posi[-1][-1]>=0 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        # maxd[i][j]表示从（0，0）到（i,j）的乘积的最大值\n",
    "        # mind[i][j]表示从（0，0）到（i，j）的乘积的最小值\n",
    "        # if grid[i][j] >= 0 maxd[i][j] = max(maxd[i-1][j],maxd[i][j-1])*grid[i][j]\n",
    "        #                    mind[i][j] = min(mind[i-1][j],mindd[i][j-1])*grid[i][j]\n",
    "        # else grid[i][j] < 0  maxd[i][j] = min(mind[i-1][j],mind[i][j-1])*grid[i][j]\n",
    "        #                      mind[i][j] = max(maxd[i-1][j],maxd[i][j-1])*grid[i][j]\n",
    "        # 初始化\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        maxd = [[0]*n for _ in range(m)]\n",
    "        mind = [[0]*n for _ in range(m)]\n",
    "        maxd[0][0] = grid[0][0]\n",
    "        mind[0][0] = grid[0][0]\n",
    "        for i in range(1,m):\n",
    "            maxd[i][0] = mind[i][0] = maxd[i-1][0]*grid[i][0]\n",
    "        for j in range(1,n):\n",
    "            maxd[0][j] = mind[0][j] = maxd[0][j-1]*grid[0][j]\n",
    "\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                if grid[i][j] >= 0:\n",
    "                    maxd[i][j] = max(maxd[i-1][j],maxd[i][j-1])*grid[i][j]\n",
    "                    mind[i][j] = min(mind[i-1][j],mind[i][j-1])*grid[i][j]\n",
    "                else:\n",
    "                    maxd[i][j] = min(mind[i-1][j],mind[i][j-1])*grid[i][j]\n",
    "                    mind[i][j] = max(maxd[i-1][j],maxd[i][j-1])*grid[i][j]\n",
    "        res = maxd[m-1][n-1]\n",
    "        if res < 0:return -1\n",
    "        return res%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        maxgt = [[0] * n for _ in range(m)]\n",
    "        minlt = [[0] * n for _ in range(m)]\n",
    "\n",
    "        maxgt[0][0] = minlt[0][0] = grid[0][0]\n",
    "        for i in range(1, n):\n",
    "            maxgt[0][i] = minlt[0][i] = maxgt[0][i - 1] * grid[0][i]\n",
    "        for i in range(1, m):\n",
    "            maxgt[i][0] = minlt[i][0] = maxgt[i - 1][0] * grid[i][0]\n",
    "        \n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if grid[i][j] >= 0:\n",
    "                    maxgt[i][j] = max(maxgt[i][j - 1], maxgt[i - 1][j]) * grid[i][j]\n",
    "                    minlt[i][j] = min(minlt[i][j - 1], minlt[i - 1][j]) * grid[i][j]\n",
    "                else:\n",
    "                    maxgt[i][j] = min(minlt[i][j - 1], minlt[i - 1][j]) * grid[i][j]\n",
    "                    minlt[i][j] = max(maxgt[i][j - 1], maxgt[i - 1][j]) * grid[i][j]\n",
    "        \n",
    "        if maxgt[m - 1][n - 1] < 0:\n",
    "            return -1\n",
    "        return maxgt[m - 1][n - 1] % mod\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        dpmx = [[0] * (m) for i in range(n)]\n",
    "        dpmi = [[0] * (m) for i in range(n)]\n",
    "        dpmx[0][0] = dpmi[0][0] = grid[0][0]\n",
    "        for i in range(1, m):\n",
    "            dpmi[0][i] = dpmx[0][i] = dpmx[0][i - 1] * grid[0][i]\n",
    "        for i in range(1, n):\n",
    "            dpmi[i][0] = dpmx[i][0] = dpmx[i - 1][0] * grid[i][0]\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, m):\n",
    "                if grid[i][j] >= 0:\n",
    "                    dpmx[i][j] = max(dpmx[i - 1][j], dpmx[i][j - 1]) * grid[i][j]\n",
    "                    dpmi[i][j] = min(dpmi[i - 1][j], dpmi[i][j - 1]) * grid[i][j]\n",
    "                else:\n",
    "                    dpmx[i][j] = min(dpmi[i - 1][j], dpmi[i][j - 1]) * grid[i][j]\n",
    "                    dpmi[i][j] = max(dpmx[i - 1][j], dpmx[i][j - 1]) * grid[i][j]\n",
    "        return dpmx[n - 1][m - 1] % (10 ** 9 + 7) if dpmx[n - 1][m - 1] >= 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        # maxg[i][j]表示从0,0出发到达i,j的乘积最大值\n",
    "        maxg = [[0]*n for _ in range(m)]\n",
    "        # ming[i][j]表示从0,0出发到达i,j的乘积最小值\n",
    "        ming = [[0]*n for _ in range(m)]\n",
    "        maxg[0][0] = grid[0][0]\n",
    "        ming[0][0] = grid[0][0]\n",
    "        for i in range(1,m):\n",
    "            maxg[i][0] = ming[i][0] = maxg[i-1][0]*grid[i][0]\n",
    "        for j in range(1,n):\n",
    "            maxg[0][j] = ming[0][j] = maxg[0][j-1]*grid[0][j]\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                if grid[i][j] >= 0:\n",
    "                    maxg[i][j] = max(maxg[i][j-1],maxg[i-1][j])*grid[i][j]\n",
    "                    ming[i][j] = min(ming[i][j-1],ming[i-1][j])*grid[i][j]\n",
    "                else:\n",
    "                    maxg[i][j] = min(ming[i][j-1],ming[i-1][j])*grid[i][j]\n",
    "                    ming[i][j] = max(maxg[i][j-1],maxg[i-1][j])*grid[i][j]\n",
    "        if maxg[m-1][n-1] < 0:return -1\n",
    "        return maxg[m-1][n-1]%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        MOD = 10**9 + 7\n",
    "        maxV = [[float('-inf')]*n for _ in range(m)]\n",
    "        minV = [[float('inf')]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x = grid[i][j]\n",
    "                if i == 0 and j == 0:\n",
    "                    maxV[i][j], minV[i][j] = grid[i][j], grid[i][j]\n",
    "                if j > 0:\n",
    "                    maxV[i][j] = max([maxV[i][j], maxV[i][j-1] * x, minV[i][j-1] * x])\n",
    "                    minV[i][j] = min([minV[i][j], maxV[i][j-1] * x, minV[i][j-1] * x])\n",
    "                if i > 0:\n",
    "                    maxV[i][j] = max([maxV[i][j], maxV[i-1][j] * x, minV[i-1][j] * x])\n",
    "                    minV[i][j] = min([minV[i][j], maxV[i-1][j] * x, minV[i-1][j] * x])\n",
    "                # print(i, j, maxV, minV)\n",
    "        return maxV[m-1][n-1] % MOD if maxV[m-1][n-1] >= 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f = [[[-inf, inf] for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                v = grid[i][j]\n",
    "                if i == 0 and j == 0:\n",
    "                    f[i][j][0] = f[i][j][1] = grid[i][j]\n",
    "                v1 = grid[i+1][j] if i + 1 < m else 0\n",
    "                v2 = grid[i][j+1] if j + 1 < n else 0\n",
    "                mx, mn = f[i][j][0], f[i][j][1]\n",
    "                f[i+1][j][0] = max(f[i+1][j][0], v1 * mx, v1 * mn)\n",
    "                f[i+1][j][1] = min(f[i+1][j][1], v1 * mx, v1 * mn)\n",
    "                f[i][j+1][0] = max(f[i][j+1][0], v2 * mx, v2 * mn)\n",
    "                f[i][j+1][1] = min(f[i][j+1][1], v2 * mx, v2 * mn)\n",
    "\n",
    "        mod = 10**9 + 7\n",
    "        return -1 if f[m-1][n-1][0] < 0 else f[m-1][n-1][0] % mod "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.num_divide = 10 ** 9 + 7\n",
    "\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        row_length, col_length = len(grid), len(grid[0])\n",
    "        if row_length == 0 or col_length == 0:\n",
    "            return 0\n",
    "\n",
    "        curr_row = curr_col = 0\n",
    "        list_record = [[[0] * 2 for _ in range(col_length)]  for _ in range(row_length)]\n",
    "        list_record[0][0][0] = list_record[0][0][1] = grid[0][0]\n",
    "\n",
    "        for row_now in range(0, row_length):\n",
    "            for col_now in range(0, col_length):\n",
    "                if row_now == 0 and col_now == 0:\n",
    "                    continue\n",
    "                elif row_now == 0:\n",
    "                    list_record[0][col_now][0] = list_record[0][col_now][1] = list_record[0][col_now - 1][0] * grid[0][col_now]\n",
    "                elif col_now == 0:\n",
    "                    list_record[row_now][0][0] = list_record[row_now][0][1] = list_record[row_now - 1][0][0] * grid[row_now][0]\n",
    "                elif row_now < row_length and col_now < col_length:\n",
    "                    if grid[row_now][col_now] >= 0:\n",
    "                        list_record[row_now][col_now][0] = max(list_record[row_now - 1][col_now][0], list_record[row_now][col_now - 1][0]) * grid[row_now][col_now]\n",
    "                        list_record[row_now][col_now][1] = min(list_record[row_now - 1][col_now][1], list_record[row_now][col_now - 1][1]) * grid[row_now][col_now]\n",
    "                    else:\n",
    "                        list_record[row_now][col_now][0] = min(list_record[row_now - 1][col_now][1],list_record[row_now][col_now - 1][1]) * grid[row_now][col_now]\n",
    "                        list_record[row_now][col_now][1] = max(list_record[row_now - 1][col_now][0],list_record[row_now][col_now - 1][0]) * grid[row_now][col_now]\n",
    "\n",
    "        if list_record[row_length - 1][col_length - 1][0] < 0:\n",
    "            return -1\n",
    "        return list_record[row_length - 1][col_length - 1][0] % self.num_divide"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dx, dy = [1, 0], [0, 1]\n",
    "        t = [[[None, None] for _ in range(n)] for _ in range(m)]\n",
    "        t[0][0] = [grid[0][0], grid[0][0]]\n",
    "        f = False\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for k in range(2):\n",
    "                    x, y = i + dx[k], j + dy[k]\n",
    "                    if x >= m or y >= n: continue\n",
    "                    minn = min(t[i][j][0] * grid[x][y], t[i][j][1] * grid[x][y])\n",
    "                    if t[x][y][0]:\n",
    "                        t[x][y][0] = min(t[x][y][0], minn)\n",
    "                    else:\n",
    "                        t[x][y][0] = minn\n",
    "                    maxx = max(t[i][j][0] * grid[x][y], t[i][j][1] * grid[x][y])\n",
    "                    if t[x][y][1]:\n",
    "                        t[x][y][1] = max(t[x][y][1], maxx)\n",
    "                    else:\n",
    "                        t[x][y][1] = maxx\n",
    "                if grid[i][j] == 0:\n",
    "                    f = True\n",
    "        return t[-1][-1][1] % (10 ** 9 + 7) if t[-1][-1][1] >= 0 else 0 if f else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mx = [[0] * n for _ in range(m)]\n",
    "        mi = [[0] * n for _ in range(m)]\n",
    "\n",
    "        mx[0][0] = mi[0][0] = grid[0][0]\n",
    "        for j in range(1, n):\n",
    "            mx[0][j] = mi[0][j] = mx[0][j - 1] * grid[0][j]\n",
    "        for i in range(1, m):\n",
    "            mx[i][0] = mi[i][0] = mi[i - 1][0] * grid[i][0]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if grid[i][j] >= 0:\n",
    "                    mx[i][j] = max(mx[i - 1][j], mx[i][j - 1]) * grid[i][j]\n",
    "                    mi[i][j] = min(mi[i - 1][j], mi[i][j - 1]) * grid[i][j]\n",
    "                else:\n",
    "                    mx[i][j] = min(mi[i - 1][j], mi[i][j - 1]) * grid[i][j]\n",
    "                    mi[i][j] = max(mx[i - 1][j], mx[i][j - 1]) * grid[i][j]\n",
    "        if mx[-1][-1] < 0:\n",
    "            return -1\n",
    "        return mx[-1][-1] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        maxgt = [[0] * n for _ in range(m)]\n",
    "        minlt = [[0] * n for _ in range(m)]\n",
    "\n",
    "        maxgt[0][0] = minlt[0][0] = grid[0][0]\n",
    "        for i in range(1, n):\n",
    "            maxgt[0][i] = minlt[0][i] = maxgt[0][i - 1] * grid[0][i]\n",
    "        for i in range(1, m):\n",
    "            maxgt[i][0] = minlt[i][0] = maxgt[i - 1][0] * grid[i][0]\n",
    "        \n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if grid[i][j] >= 0:\n",
    "                    maxgt[i][j] = max(maxgt[i][j - 1], maxgt[i - 1][j]) * grid[i][j]\n",
    "                    minlt[i][j] = min(minlt[i][j - 1], minlt[i - 1][j]) * grid[i][j]\n",
    "                else:\n",
    "                    maxgt[i][j] = min(minlt[i][j - 1], minlt[i - 1][j]) * grid[i][j]\n",
    "                    minlt[i][j] = max(maxgt[i][j - 1], maxgt[i - 1][j]) * grid[i][j]\n",
    "        \n",
    "        if maxgt[m - 1][n - 1] < 0:\n",
    "            return -1\n",
    "        return maxgt[m - 1][n - 1] % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        if not grid:\n",
    "            return 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp1 = [[1]*n for _ in range(m)]\n",
    "        dp2 = [[1]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not i and not j:\n",
    "                    dp1[i][j] = grid[i][j]\n",
    "                    dp2[i][j] = grid[i][j]\n",
    "                if i == 0 and j != 0:\n",
    "                    dp1[i][j] = dp1[i][j-1]*grid[i][j]\n",
    "                    dp2[i][j] = dp2[i][j-1]*grid[i][j]\n",
    "                if i != 0 and j == 0:\n",
    "                    dp1[i][j] = dp1[i-1][j] * grid[i][j]\n",
    "                    dp2[i][j] = dp2[i-1][j] * grid[i][j]\n",
    "                elif i != 0 and j != 0:\n",
    "                    dp1[i][j] = max(dp1[i-1][j]*grid[i][j], dp1[i][j-1]*grid[i][j], dp2[i-1][j]*grid[i][j], dp2[i][j-1]*grid[i][j])\n",
    "                    dp2[i][j] = min(dp1[i-1][j]*grid[i][j], dp1[i][j-1]*grid[i][j], dp2[i-1][j]*grid[i][j], dp2[i][j-1]*grid[i][j])      \n",
    "        return -1 if dp1[-1][-1] < 0 else dp1[-1][-1]%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f = [[inf] * (n+1) for _ in range(m+1)] # 最小负积\n",
    "        g = [[-inf] * (n+1) for _ in range(m+1)] # 最大正积\n",
    "        f[0][1] = g[0][1] = 1\n",
    "        # 最小负积=之前的最小负积*正数  或  之前的最大正积*负数\n",
    "        # 最大正积=之前的最小负积*负数  或  之前的最大正积*正数\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] > 0:\n",
    "                    g[i+1][j+1] = max(g[i][j+1], g[i+1][j]) * grid[i][j]\n",
    "                    f[i+1][j+1] = min(f[i][j+1], f[i+1][j]) * grid[i][j]\n",
    "                else:\n",
    "                    g[i+1][j+1] = min(f[i][j+1], f[i+1][j]) * grid[i][j]\n",
    "                    f[i+1][j+1] = max(g[i][j+1], g[i+1][j]) * grid[i][j]\n",
    "        # for x in g:\n",
    "        #     print(x)\n",
    "        return g[m][n] % MOD if g[m][n] >= 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        \n",
    "        dp0 = [[float(\"-inf\")] * n for _ in range(m)]\n",
    "        dp0[0][0] = grid[0][0]\n",
    "        for i in range(1, n):\n",
    "            dp0[0][i] = dp0[0][i-1] * grid[0][i]\n",
    "        for i in range(1, m):\n",
    "            dp0[i][0] = dp0[i-1][0] * grid[i][0]\n",
    "\n",
    "        dp1 = [[float(\"inf\")] * n for _ in range(m)]\n",
    "        dp1[0][0] = grid[0][0]\n",
    "        for i in range(1, n):\n",
    "            dp1[0][i] = dp1[0][i-1] * grid[0][i]\n",
    "        for i in range(1, m):\n",
    "            dp1[i][0] = dp1[i-1][0] * grid[i][0]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp0[i][j] = max(dp0[i-1][j] * grid[i][j], \n",
    "                                dp0[i][j-1] * grid[i][j],\n",
    "                                dp1[i-1][j] * grid[i][j], \n",
    "                                dp1[i][j-1] * grid[i][j])\n",
    "                dp1[i][j] = min(dp1[i-1][j] * grid[i][j], \n",
    "                                dp1[i][j-1] * grid[i][j],\n",
    "                                dp0[i-1][j] * grid[i][j], \n",
    "                                dp0[i][j-1] * grid[i][j])\n",
    "        \n",
    "        if dp0[-1][-1] < 0:\n",
    "            return -1\n",
    "        else:\n",
    "            return int(dp0[-1][-1] % (1e9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        ll = [[1]*m for _ in range(n)]\n",
    "        lm = [[1]*m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if not i and not j:\n",
    "                    ll[i][j] = grid[i][j]\n",
    "                    lm[i][j] = grid[i][j]\n",
    "                if i == 0 and j !=0:\n",
    "                    ll[i][j] = ll[i][j-1] * grid[i][j]\n",
    "                    lm[i][j] = lm[i][j-1] * grid[i][j]\n",
    "                if i != 0 and j ==0:\n",
    "                    ll[i][j] = ll[i-1][j] * grid[i][j]\n",
    "                    lm[i][j] = lm[i-1][j] * grid[i][j]\n",
    "                elif i!=0 and j!= 0:\n",
    "                    ll[i][j] = min(ll[i-1][j]*grid[i][j],lm[i-1][j]*grid[i][j],ll[i][j-1]*grid[i][j],lm[i][j-1]*grid[i][j])\n",
    "                    lm[i][j] = max(ll[i-1][j]*grid[i][j],lm[i-1][j]*grid[i][j],ll[i][j-1]*grid[i][j],lm[i][j-1]*grid[i][j])\n",
    "        return -1 if lm[-1][-1] < 0 else lm[-1][-1]%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        # maxg[i][j]表示从0,0出发到达i,j的乘积最大值\n",
    "        maxg = [[0]*n for _ in range(m)]\n",
    "        # ming[i][j]表示从0,0出发到达i,j的乘积最小值\n",
    "        ming = [[0]*n for _ in range(m)]\n",
    "        maxg[0][0] = grid[0][0]\n",
    "        ming[0][0] = grid[0][0]\n",
    "        for i in range(1,m):\n",
    "            maxg[i][0] = ming[i][0] = maxg[i-1][0]*grid[i][0]\n",
    "        for j in range(1,n):\n",
    "            maxg[0][j] = ming[0][j] = maxg[0][j-1]*grid[0][j]\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                if grid[i][j] > 0:\n",
    "                    maxg[i][j] = max(maxg[i][j-1],maxg[i-1][j])*grid[i][j]\n",
    "                    ming[i][j] = min(ming[i][j-1],ming[i-1][j])*grid[i][j]\n",
    "                else:\n",
    "                    maxg[i][j] = min(ming[i][j-1],ming[i-1][j])*grid[i][j]\n",
    "                    ming[i][j] = max(maxg[i][j-1],maxg[i-1][j])*grid[i][j]\n",
    "        if maxg[m-1][n-1] < 0:return -1\n",
    "        return maxg[m-1][n-1]%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dp = [[(0, 0) for _ in range(n)] for _ in range(m)]\n",
    "        dp[0][0] = (grid[0][0], grid[0][0])\n",
    "        for i in range(1, m):\n",
    "            dp[i][0] = (max(dp[i-1][0][0] * grid[i][0], dp[i-1][0][1] * grid[i][0]), min(dp[i-1][0][0] * grid[i][0], dp[i-1][0][1] * grid[i][0]))\n",
    "        for j in range(1, n):\n",
    "            dp[0][j] = (max(dp[0][j-1][0] * grid[0][j], dp[0][j-1][1] * grid[0][j]), min(dp[0][j-1][0] * grid[0][j], dp[0][j-1][1] * grid[0][j]))\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                a1 = dp[i-1][j][0] * grid[i][j]\n",
    "                a2 = dp[i-1][j][1] * grid[i][j]\n",
    "                a3 = dp[i][j-1][0] * grid[i][j]\n",
    "                a4 = dp[i][j-1][1] * grid[i][j]\n",
    "                dp[i][j] = (max(a1, a2, a3, a4), min(a1, a2, a3, a4))\n",
    "        result = dp[m-1][n-1][0]\n",
    "        if result >= 0:\n",
    "            return result % 1000000007\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dp = [[[0, 0] * 2 for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "        zero_flag = False\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    zero_flag = True\n",
    "                if i == 0 and j == 0:\n",
    "                    if grid[i][j] >= 0:\n",
    "                        dp[i + 1][j + 1][0] = grid[i][j]\n",
    "                    else:\n",
    "                        dp[i + 1][j + 1][1] = grid[i][j]\n",
    "                else:\n",
    "                    if grid[i][j] >= 0:\n",
    "                        dp[i + 1][j + 1][0] = max(dp[i][j + 1][0], dp[i + 1][j][0]) * grid[i][j]\n",
    "                        dp[i + 1][j + 1][1] = min(dp[i][j + 1][1], dp[i + 1][j][1]) * grid[i][j]\n",
    "                    else:\n",
    "                        dp[i + 1][j + 1][0] = min(dp[i][j + 1][1], dp[i + 1][j][1]) * grid[i][j]\n",
    "                        dp[i + 1][j + 1][1] = max(dp[i][j + 1][0], dp[i + 1][j][0]) * grid[i][j]\n",
    "\n",
    "        ans = dp[-1][-1][0]\n",
    "        if ans > 0:\n",
    "            return ans % MOD\n",
    "        elif ans == 0:\n",
    "            if zero_flag:\n",
    "                return 0\n",
    "            else:\n",
    "                return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        # maxg[i][j]表示从0,0出发到达i,j的乘积最大值\n",
    "        maxg = [[0]*n for _ in range(m)]\n",
    "        # ming[i][j]表示从0,0出发到达i,j的乘积最小值\n",
    "        ming = [[0]*n for _ in range(m)]\n",
    "        maxg[0][0] = grid[0][0]\n",
    "        ming[0][0] = grid[0][0]\n",
    "        for i in range(1,m):\n",
    "            maxg[i][0] = ming[i][0] = maxg[i-1][0]*grid[i][0]\n",
    "        for j in range(1,n):\n",
    "            maxg[0][j] = ming[0][j] = maxg[0][j-1]*grid[0][j]\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                if grid[i][j] >=0:\n",
    "                    maxg[i][j] = max(maxg[i][j-1],maxg[i-1][j])*grid[i][j]\n",
    "                    ming[i][j] = min(ming[i][j-1],ming[i-1][j])*grid[i][j]\n",
    "                else:\n",
    "                    maxg[i][j] = min(ming[i][j-1],ming[i-1][j])*grid[i][j]\n",
    "                    ming[i][j] = max(maxg[i][j-1],maxg[i-1][j])*grid[i][j]\n",
    "        if maxg[m-1][n-1] < 0:return -1\n",
    "        return maxg[m-1][n-1]%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, nums: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n, m = len(nums), len(nums[0])\n",
    "        # f[i][j][0] 从(0, 0)到坐标(i, j)最大值路径的情况\n",
    "        # f[i][j][1] 从(0, 0)到坐标(i, j)最小值路径的情况\n",
    "        f = [[[1] * 2 for _ in range(m)] for _ in range(n)]\n",
    "        f[0][0][0] = f[0][0][1] = nums[0][0]\n",
    "        for i in range(1, n):\n",
    "            f[i][0][0] = f[i][0][1] = f[i - 1][0][0] * nums[i][0]\n",
    "        for j in range(1, m):\n",
    "            f[0][j][0] = f[0][j][1] = f[0][j - 1][0] * nums[0][j]\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, m):\n",
    "                if nums[i][j] >= 0:\n",
    "                    f[i][j][0] = max(f[i - 1][j][0], f[i][j - 1][0]) * nums[i][j]\n",
    "                    f[i][j][1] = min(f[i - 1][j][1], f[i][j - 1][1]) * nums[i][j]\n",
    "                else:\n",
    "                    f[i][j][0] = min(f[i - 1][j][1], f[i][j - 1][1]) * nums[i][j]\n",
    "                    f[i][j][1] = max(f[i - 1][j][0], f[i][j - 1][0]) * nums[i][j]\n",
    "        print(f)\n",
    "        if f[n - 1][m - 1][0] < 0:\n",
    "            return -1\n",
    "        return f[n - 1][m - 1][0] % MOD\n",
    "                    \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "\n",
    "        dp = [[[1, 1] for _ in range(col)] for _ in range(row)]\n",
    "        # print(dp)\n",
    "        dp[0][0][0] = dp[0][0][1] = grid[0][0]\n",
    "        for i in range(1,col):\n",
    "            dp[0][i][0] = dp[0][i][1] = dp[0][i-1][0] * grid[0][i]\n",
    "        for i in range(1, row):\n",
    "            dp[i][0][0] = dp[i][0][1] = dp[i-1][0][0] * grid[i][0]\n",
    "\n",
    "        for i in range(1, row):\n",
    "            for j in range(1, col):\n",
    "                maxProduct = max(dp[i - 1][j][0], dp[i][j - 1][0])\n",
    "                minProduct = min(dp[i - 1][j][1], dp[i][j - 1][1])\n",
    "                num = grid[i][j]\n",
    "                if num < 0:\n",
    "                    maxProduct, minProduct = minProduct, maxProduct\n",
    "\n",
    "                maxProduct *= num\n",
    "                minProduct *= num\n",
    "                dp[i][j] = [maxProduct, minProduct]\n",
    "\n",
    "        # print(dp)\n",
    "        return dp[-1][-1][0] % (10 ** 9 + 7) if dp[-1][-1][0] >= 0 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = 10**9+7\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[[0,0] for _ in range(n)] for _ in range(m)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if(i == 0 and j == 0):\n",
    "                    dp[0][0] = [grid[0][0],grid[0][0]]\n",
    "                elif(i == 0):\n",
    "                    dp[i][j][0] = dp[i][j-1][0]*grid[i][j]\n",
    "                    dp[i][j][1] = dp[i][j-1][1]*grid[i][j]\n",
    "                elif(j == 0):\n",
    "                    dp[i][j][0] = dp[i-1][j][0]*grid[i][j]\n",
    "                    dp[i][j][1] = dp[i-1][j][1]*grid[i][j]        \n",
    "                else:\n",
    "                    dp[i][j][0] = min(dp[i-1][j][0]*grid[i][j], dp[i-1][j][1]*grid[i][j], dp[i][j-1][0]*grid[i][j], dp[i][j-1][1]*grid[i][j])\n",
    "                    dp[i][j][1] = max(dp[i-1][j][0]*grid[i][j], dp[i-1][j][1]*grid[i][j], dp[i][j-1][0]*grid[i][j], dp[i][j-1][1]*grid[i][j])\n",
    "        return dp[m-1][n-1][1] % M if dp[m-1][n-1][1] >= 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        maxgt = [[0] * n for _ in range(m)]\n",
    "        minlt = [[0] * n for _ in range(m)]\n",
    "\n",
    "        maxgt[0][0] = minlt[0][0] = grid[0][0]\n",
    "        for i in range(1, n):\n",
    "            maxgt[0][i] = minlt[0][i] = maxgt[0][i - 1] * grid[0][i]\n",
    "        for i in range(1, m):\n",
    "            maxgt[i][0] = minlt[i][0] = maxgt[i - 1][0] * grid[i][0]\n",
    "        \n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if grid[i][j] >= 0:\n",
    "                    maxgt[i][j] = max(maxgt[i][j - 1], maxgt[i - 1][j]) * grid[i][j]\n",
    "                    minlt[i][j] = min(minlt[i][j - 1], minlt[i - 1][j]) * grid[i][j]\n",
    "                else:\n",
    "                    maxgt[i][j] = min(minlt[i][j - 1], minlt[i - 1][j]) * grid[i][j]\n",
    "                    minlt[i][j] = max(maxgt[i][j - 1], maxgt[i - 1][j]) * grid[i][j]\n",
    "        \n",
    "        if maxgt[m - 1][n - 1] < 0:\n",
    "            return -1\n",
    "        return maxgt[m - 1][n - 1] % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        maxgt = [[0] * n for _ in range(m)]\n",
    "        minlt = [[0] * n for _ in range(m)]\n",
    "\n",
    "        maxgt[0][0] = minlt[0][0] = grid[0][0]\n",
    "        for i in range(1, n):\n",
    "            maxgt[0][i] = minlt[0][i] = maxgt[0][i - 1] * grid[0][i]\n",
    "        for i in range(1, m):\n",
    "            maxgt[i][0] = minlt[i][0] = maxgt[i - 1][0] * grid[i][0]\n",
    "        \n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if grid[i][j] >= 0:\n",
    "                    maxgt[i][j] = max(maxgt[i][j - 1], maxgt[i - 1][j]) * grid[i][j]\n",
    "                    minlt[i][j] = min(minlt[i][j - 1], minlt[i - 1][j]) * grid[i][j]\n",
    "                else:\n",
    "                    maxgt[i][j] = min(minlt[i][j - 1], minlt[i - 1][j]) * grid[i][j]\n",
    "                    minlt[i][j] = max(maxgt[i][j - 1], maxgt[i - 1][j]) * grid[i][j]\n",
    "        \n",
    "        if maxgt[m - 1][n - 1] < 0:\n",
    "            return -1\n",
    "        return maxgt[m - 1][n - 1] % mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        dp = [[[0, 0] for _ in range(len(grid[0]))] for _ in range(len(grid))] #min, max\n",
    "\n",
    "        dp[0][0][0] = grid[0][0]\n",
    "        dp[0][0][1] = grid[0][0]\n",
    "        for i in range(1, len(grid)):\n",
    "            if grid[i][0] >= 0:\n",
    "                dp[i][0][0] = dp[i-1][0][0] * grid[i][0]\n",
    "                dp[i][0][1] = dp[i-1][0][1] * grid[i][0]\n",
    "            else:\n",
    "                dp[i][0][0] = dp[i-1][0][1] * grid[i][0]\n",
    "                dp[i][0][1] = dp[i-1][0][0] * grid[i][0]\n",
    "        for i in range(1, len(grid[0])):\n",
    "            if grid[0][i] >= 0:\n",
    "                dp[0][i][0] = dp[0][i-1][0] * grid[0][i]\n",
    "                dp[0][i][1] = dp[0][i-1][1] * grid[0][i]\n",
    "            else:\n",
    "                dp[0][i][0] = dp[0][i-1][1] * grid[0][i]\n",
    "                dp[0][i][1] = dp[0][i-1][0] * grid[0][i]\n",
    "\n",
    "        for i in range(1, len(grid)):\n",
    "            for j in range(1, len(grid[0])):\n",
    "                if grid[i][j] >=0:\n",
    "                    dp[i][j][0] = min(dp[i][j-1][0], dp[i-1][j][0]) * grid[i][j]\n",
    "                    dp[i][j][1] = max(dp[i][j-1][1], dp[i-1][j][1]) * grid[i][j]\n",
    "                else:\n",
    "                    dp[i][j][0] = max(dp[i][j-1][1], dp[i-1][j][1]) * grid[i][j]\n",
    "                    dp[i][j][1] = min(dp[i][j-1][0], dp[i-1][j][0]) * grid[i][j]\n",
    "\n",
    "        if dp[-1][-1][1] >=0:\n",
    "            return dp[-1][-1][1] % (10**9 + 7)\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        #------- 动态规划 dp 维持某个位置的最大值 最小值\n",
    "        r, c = len(grid), len(grid[0])\n",
    "        T = [[0 for _ in range(c)] for _ in range(r)]\n",
    "        D = [[0 for _ in range(c)] for _ in range(r)]\n",
    "        T[0][0] = D[0][0] = grid[0][0]    #最左上角\n",
    "        for j in range(1, c):     #第0行\n",
    "            T[0][j] = D[0][j] = T[0][j-1] * grid[0][j]\n",
    "        for i in range(1, r):     #第0列\n",
    "            T[i][0] = D[i][0] = T[i-1][0] * grid[i][0]\n",
    "        \n",
    "        for i in range(1, r):\n",
    "            for j in range(1, c):\n",
    "                x = grid[i][j]\n",
    "                if x >= 0:\n",
    "                    T[i][j] = max(T[i-1][j], T[i][j-1]) * x\n",
    "                    D[i][j] = min(D[i-1][j], D[i][j-1]) * x\n",
    "                else:\n",
    "                    T[i][j] = min(D[i-1][j], D[i][j-1]) * x\n",
    "                    D[i][j] = max(T[i-1][j], T[i][j-1]) * x\n",
    "\n",
    "        return T[-1][-1] % (10**9+7) if T[-1][-1] >= 0 else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        maxp = [[0] * n for _ in range(m)]\n",
    "        minp = [[0] * n for _ in range(m)]\n",
    "\n",
    "        maxp[0][0] = grid[0][0]\n",
    "        minp[0][0] = grid[0][0]\n",
    "\n",
    "        for j in range(1, n):\n",
    "            maxp[0][j] = maxp[0][j-1] * grid[0][j]\n",
    "            minp[0][j] = minp[0][j-1] * grid[0][j]\n",
    "        \n",
    "        for i in range(1, m):\n",
    "            maxp[i][0] = maxp[i-1][0] * grid[i][0] \n",
    "            minp[i][0] = minp[i-1][0] * grid[i][0]\n",
    "        \n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                x = grid[i][j]\n",
    "                if x >= 0:\n",
    "                    maxp[i][j] = max(maxp[i-1][j], maxp[i][j-1]) * x\n",
    "                    minp[i][j] = min(minp[i-1][j], minp[i][j-1]) * x\n",
    "                else:\n",
    "                    maxp[i][j] = min(minp[i-1][j], minp[i][j-1]) * x\n",
    "                    minp[i][j] = max(maxp[i-1][j], maxp[i][j-1]) * x\n",
    "        print(maxp)\n",
    "        print(minp)\n",
    "        return maxp[m-1][n-1] % mod if maxp[m-1][n-1] >= 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f = [[[0] * 2 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                v = grid[i][j]\n",
    "                if i == 0 and j == 0:\n",
    "                    f[i][j][0] = f[i][j][1] = grid[i][j]\n",
    "                elif i == 0:\n",
    "                    mx2, mn2 = f[i][j-1][0], f[i][j - 1][1]\n",
    "                    mx = max(mx2 * v, mn2 * v)\n",
    "                    mn = min( mx2 * v, mn2 * v)\n",
    "                    f[i][j][0], f[i][j][1] = mx, mn\n",
    "                elif j == 0:\n",
    "                    mx1, mn1 = f[i-1][j][0], f[i-1][j][1]\n",
    "                    mx = max(mx1 * v, mn1 * v)\n",
    "                    mn = min(mx1 * v, mn1 * v)\n",
    "                    f[i][j][0], f[i][j][1] = mx, mn\n",
    "                else:\n",
    "                    mx1, mn1 = f[i-1][j][0], f[i-1][j][1]\n",
    "                    mx2, mn2 = f[i][j-1][0], f[i][j - 1][1]\n",
    "                    mx = max(mx1 * v, mn1 * v, mx2 * v, mn2 * v)\n",
    "                    mn = min(mx1 * v, mn1 * v, mx2 * v, mn2 * v)\n",
    "                    f[i][j][0], f[i][j][1] = mx, mn\n",
    "        mod = 10**9 + 7\n",
    "        return -1 if f[-1][-1][0] < 0 else f[-1][-1][0] % mod "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "\n",
    "        dp = [[[1,1] for _ in range(col)] for _ in range(row)]         \n",
    "        # print(dp)             \n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if i == 0 and j == 0:\n",
    "                    dp[0][0] = [grid[0][0], grid[0][0]]\n",
    "                    continue\n",
    "                if i == 0 and j > 0:\n",
    "                    maxProduct, minProduct = dp[0][j-1]\n",
    "                elif i > 0 and j == 0:\n",
    "                    maxProduct, minProduct = dp[i-1][0]\n",
    "                else:\n",
    "                    maxProduct = max(dp[i-1][j][0], dp[i][j-1][0])\n",
    "                    minProduct = min(dp[i-1][j][1], dp[i][j-1][1])\n",
    "                \n",
    "                num = grid[i][j]\n",
    "                if num < 0:\n",
    "                    maxProduct, minProduct = minProduct, maxProduct\n",
    "            \n",
    "                maxProduct *= num\n",
    "                minProduct *= num\n",
    "\n",
    "                dp[i][j] = [maxProduct, minProduct]\n",
    "\n",
    "        print(dp)\n",
    "        return dp[-1][-1][0] % (10 ** 9 + 7) if dp[-1][-1][0] >= 0 else -1\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\r\n",
    "        # 存下到某个的最大正路径和绝对值最大的负路径和 \r\n",
    "        m, n = len(grid), len(grid[0])\r\n",
    "        dp = [[[0] * 2 for _ in range(n)] for __ in range(m)]\r\n",
    "        if grid[0][0] > 0:\r\n",
    "            dp[0][0][0] = grid[0][0]\r\n",
    "        else : dp[0][0][1] = grid[0][0]\r\n",
    "\r\n",
    "        flag = any(grid[x][y] == 0 for x in range(m) for y in range(n))\r\n",
    "        for i in range(1, m):\r\n",
    "            if grid[i][0] > 0:\r\n",
    "                dp[i][0][0] = dp[i-1][0][0] * grid[i][0]\r\n",
    "                dp[i][0][1] = dp[i-1][0][1] * grid[i][0]\r\n",
    "            else: \r\n",
    "                dp[i][0][0] = dp[i-1][0][1] * grid[i][0]\r\n",
    "                dp[i][0][1] = dp[i-1][0][0] * grid[i][0]\r\n",
    "        for j in range(1, n):\r\n",
    "            if grid[0][j] > 0:\r\n",
    "                dp[0][j][0] = dp[0][j-1][0] * grid[0][j] \r\n",
    "                dp[0][j][1] = dp[0][j-1][1] * grid[0][j]\r\n",
    "            else:\r\n",
    "                dp[0][j][0] = dp[0][j-1][1] * grid[0][j] \r\n",
    "                dp[0][j][1] = dp[0][j-1][0] * grid[0][j] \r\n",
    "\r\n",
    "        for i in range(1, m):\r\n",
    "            for j in range(1, n):\r\n",
    "                if grid[i][j] > 0:\r\n",
    "                    dp[i][j][0] = max(dp[i-1][j][0], dp[i][j-1][0]) * grid[i][j]\r\n",
    "                    dp[i][j][1] = min(dp[i-1][j][1], dp[i][j-1][1]) * grid[i][j]\r\n",
    "                else:\r\n",
    "                    dp[i][j][0] = min(dp[i-1][j][1], dp[i][j-1][1]) * grid[i][j]\r\n",
    "                    dp[i][j][1] = max(dp[i-1][j][0], dp[i][j-1][0]) * grid[i][j]\r\n",
    "        if  dp[m - 1][n -1][0] == 0:\r\n",
    "            if flag:\r\n",
    "                return 0 \r\n",
    "            return -1\r\n",
    "        return dp[-1][-1][0] % (10**9+7)\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProductPath(self, grid: List[List[int]]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        products = [[[0,0] for i in range(n)] for j in range(m)]\n",
    "        zeroFlag = False\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    zeroFlag = True\n",
    "                if grid[i][j] >= 0:\n",
    "                    if i != 0 and j != 0:\n",
    "                        products[i][j][0] = max(products[i - 1][j][0], products[i][j - 1][0]) * grid[i][j]\n",
    "                        products[i][j][1] = min(products[i - 1][j][1], products[i][j - 1][1]) * grid[i][j]\n",
    "                    elif i == 0 and j == 0:\n",
    "                        products[i][j][0] = grid[i][j]\n",
    "                        products[i][j][1] = 0\n",
    "                    elif i == 0:\n",
    "                        products[i][j][0] = products[i][j - 1][0] * grid[i][j]\n",
    "                        products[i][j][1] = products[i][j - 1][1] * grid[i][j]\n",
    "                    else:\n",
    "                        products[i][j][1] = products[i - 1][j][1] * grid[i][j]\n",
    "                        products[i][j][0] = products[i - 1][j][0] * grid[i][j]\n",
    "                else:\n",
    "                    if i != 0 and j != 0:\n",
    "                        products[i][j][0] = min(products[i - 1][j][1], products[i][j - 1][1]) * grid[i][j]\n",
    "                        products[i][j][1] = max(products[i - 1][j][0], products[i][j - 1][0]) * grid[i][j]\n",
    "                    elif i == 0 and j == 0:\n",
    "                        products[i][j][1] = grid[i][j]\n",
    "                        products[i][j][0] = 0\n",
    "                    elif i == 0:\n",
    "                        products[i][j][0] = products[i][j - 1][1] * grid[i][j]\n",
    "                        products[i][j][1] = products[i][j - 1][0] * grid[i][j]\n",
    "                    else:\n",
    "                        products[i][j][1] = products[i - 1][j][0] * grid[i][j]\n",
    "                        products[i][j][0] = products[i - 1][j][1] * grid[i][j]\n",
    "\n",
    "\n",
    "        return -1 if products[m - 1][n - 1][0] == 0 and zeroFlag == False else products[m - 1][n - 1][0] % mod"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
